/* 

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

// 中序遍历，应用中序遍历的先left子节点->当前节点->right子节点的特点和搜索树left < middle < right的特点结合
var isValidBST = function (root) {
    const helper = (root, lower, upper) => {
        if (root === null) {
            return true;
        }
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
    }

    return helper(root, -Infinity, Infinity);
};

var isValidBST = function (root) {
    let pre = -Infinity;
    let isBST = function (root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isBST(root.right);
    }

    return isBST(root);
};

// 非递归实现
var isValidBST = function (root) {
    if (root == null) return true;
    let queue = [root];
    let min = Number.MIN_SAFE_INTEGER;
    let max = Number.MAX_SAFE_INTEGER;
    root.max = max;
    root.min = min;
    while (queue.length) {
        let node = queue.pop();
        if (node.val <= node.min || node.val >= node.max)
            return false;
        if (node.left) {
            queue.push(node.left);
            // 更新上下界
            node.left.max = node.val;
            node.left.min = node.min;
        }
        if (node.right) {
            queue.push(node.right);
            // 更新上下界
            node.right.max = node.max;
            node.right.min = node.val;
        }
    }
    return true;
};